﻿// 1092. 最短公共超序列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <vector>

using namespace std;
/*
https://leetcode.cn/problems/shortest-common-supersequence/

给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。
如果答案不止一个，则可以返回满足条件的 任意一个 答案。
如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。


示例 1：
输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。

示例 2：
输入：str1 = "aaaaaaaa", str2 = "aaaaaaaa"
输出："aaaaaaaa"


提示：
1 <= str1.length, str2.length <= 1000
str1 和 str2 都由小写英文字母组成。
*/
//
//class Solution {
//public:
//    vector<vector<int>> dp;
//    string shortestCommonSupersequence(string s1, string s2) {
//        dp.resize(1010, vector<int>(1010, 0x3f3f3f3f));
//        s1.insert(s1.begin(), '#');  s2.insert(s2.begin(),'@');
//
//        for (int i = 0; i < s1.size(); i++) { dp[i][0] = i; }
//        for (int j = 0; j < s2.size(); j++) { dp[0][j] = j; }
//
//        for (int i = 1; i < s1.size(); i++) {
//            for (int j = 1; j < s2.size(); j++) {
//                if (s1[i] == s2[j]) {
//                    dp[i][j] = dp[i - 1][j - 1] + 1;
//                }
//                else {
//                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
//                }
//            }
//        }
//
//        string ans;
//        int a = s1.size() - 1; int b = s2.size() - 1;
//
//        while (a > 0 && b > 0) {
//            if (s1[a] == s2[b]) {
//                ans += s1[a];
//                a--; b--;
//            }
//            else if (dp[a][b] == dp[a - 1][b] + 1) {
//                ans += s1[a]; a--;
//            }
//            else if (dp[a][b] == dp[a][b - 1] + 1) {
//                ans += s2[b]; b--;
//            }
//        }
//        reverse(ans.begin(), ans.end());
//        if (a > 0) {
//            ans = s1.substr(1,a) + ans;
//        }
//        if (b > 0) {
//            ans = s2.substr(1,b) + ans;
//        }
//
//        return ans;
//    }
//};

class Solution {
public:
    vector<vector<int>> dp;
    string shortestCommonSupersequence(string s1, string s2) {
        dp.resize(1010, vector<int>(1010, 0x3f3f3f3f));
        s1.insert(s1.begin(), '#');  s2.insert(s2.begin(), '@');

        for (int i = 0; i < s1.size(); i++) dp[i][0] = 0;
        for (int i = 0; i < s1.size(); i++) dp[0][i] = i;

        for (int i = 1; i < s1.size(); i++) {
            for (int j = 1; j < s2.size(); j++) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = min(dp[i][j - 1]+1, dp[i - 1][j]);
                }
            }
        }

        string ans;
        int a = s1.size() - 1; int b = s2.size() - 1;
        while (a > 0 && b > 0) {
            if (s1[a] == s2[b] && dp[a][b]==dp[a-1][b-1]) {
                ans += s1[a]; a--; b--;
            }
            else if (dp[a][b] == dp[a][b - 1] + 1) {
                ans += s2[b]; b--;
            }
            else {
                ans += s1[a]; a--;
            }
        }

        reverse(ans.begin(), ans.end());
        if (a > 0) {
            ans = s1.substr(1, a) + ans;
        }

        if (b > 0) {
            ans = s2.substr(1, b) + ans;
        }

        return ans;
    }
};


int main()
{
    Solution s;

    s.shortestCommonSupersequence("abac","cab");
}
 